﻿// 369. 质数路径 Prime Path（挑战程序设计竞赛）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <queue>

using namespace std;

/*
https://www.papamelon.com/problem/369


给定两个均是4 位的质数a,b（保证没有前缀0)。

每次可以修改a 中的一位数字，使其变为一个新的数字，且该数字必须也是质数。

最终，我们要将a 变成b。

输出最少需要多少次变化。

输入
第一行一个整数T(1≤T≤100)，表示有多少组测试数据
每组测试数据占据一行，两个整数a,b
输出
每组测试数据输出一行，一个整数，表示从a 到b 需要多少次变化
样例 1
输入
3
1033 8179
1373 8017
1033 1033
输出
6
7
0
*/

/*
4
8929 3229
8929 3229
8929 3229
8929 3229
*/

const int N = 10010;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
unordered_map<int,int> mm;

int start, finish;

void get_primes_sp(int n) {
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			primes[cnt++] = i;
			if (i >= 1000 && i <= 9999) {
				mm[i]=0;
			}
		}
		for (int j = 0; primes[j] <= n / i; j++) {
			st[primes[j] * i] = true;
			if (i % primes[j] == 0) break;
		}
	}
}


void extend(int n, int step, int ex, queue<pair<int, int>>& q) {
	int cpy = n; int div = ex * 10;
	cpy = n;
	while (cpy % div / ex > 0) {
		cpy -= ex;
		if (mm.count(cpy) != 0 && mm[cpy] == 0) {
			mm[cpy] = 1;
			q.push({ cpy,step + 1 });
		}
	}

	cpy = n;
	while (cpy % div / ex < 9) {
		cpy += ex;
		if (mm.count(cpy) != 0 && mm[cpy] == 0) {
			mm[cpy] = 1;
			q.push({ cpy,step + 1 });
		}
	}
}

void solve() {
	//init
	for (auto& e : mm) {e.second = 0;}
	cin >> start >> finish;
	queue<pair<int, int>> q;
	q.push({start,0});
	mm[start] = 1;
	while (!q.empty()) {
		int t = q.front().first; int step = q.front().second;
		q.pop();
		
		if (t == finish) {
			cout << step << endl;
			return;
		}
		//扩展 个位 十位 百位 千位 +- 1 10 100 1000
		extend(t,step,1,q);
		extend(t, step, 10,q);
		extend(t, step, 100,q);
		extend(t, step, 1000,q);
	}
}

int main()
{
	get_primes_sp(10000);
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		solve();
	}

	return 0;
}

 